<?php
/**
 * User: helloJiu
 * Date: 2021/11/2
 * Time: 14:19
 */

namespace App\Algorithm\DP;


class FindTargetSumWays
{
    /**
     * https://leetcode-cn.com/problems/target-sum/
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function findTargetSumWays($nums, $target)
    {
        $sum = array_sum($nums);
        // $sum = $right + $left
        // $target = $left - $right
        // ---> $left = ($sum + $target) / 2
        if (($sum + $target) % 2 != 0) {
            return 0;
        }
        $left = ($sum + $target) / 2;

        // 小于0, 肯定凑不够
        if ($left < 0) {
            return 0;
        }
        // 找到和是$left有多少种方式

        $dp = [];
        // $dp[$w]: 表示和是$w时有$dp[$w]种方式
        for ($w = 0; $w <= $left; $w++) {
            $dp[$w] = 0;
        }

        $dp[0] = 1;

        for ($i = 1; $i <= count($nums); $i++) {
            if ($nums[$i - 1] > $left) continue;
            // $w需要包含0, 因为0也可以凑够
            for ($w = $left; $w >= 0; $w--) {
                $remain_w = $w - $nums[$i - 1];
                // $dp[$w]: $i之前元素得到的方式
                // 累积上遍历到$i得到的方式: $dp[$remain_w]
                $dp[$w] = $dp[$remain_w] + $dp[$w];

            }
        }
        return $dp[$left];
    }
}